package com.lw.leetcode.arr.b;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * arr
 * 2400. 恰好移动 k 步到达某一位置的方法数目
 *
 * @author liw
 * @version 1.0
 * @date 2022/9/4 14:24
 */
public class NumberOfWays {

    public static void main(String[] args) {
        NumberOfWays test = new NumberOfWays();

        int st = 1;
        int end = 2;
        int k = 3;

        int i = test.numberOfWays(st, end, k);
        System.out.println(i);
    }

    public int numberOfWays(int startPos, int endPos, int k) {
        int st = startPos - k;
        int end = startPos + k;
        if (endPos < st || endPos > end) {
            return 0;
        }
        if (endPos == st || endPos == end) {
            return 1;
        }
        int length = end - st + 1;
        int c = 0 - st;
        startPos += c;
        endPos += c;
        long[] arr1 = new long[length];
        long[] arr2 = new long[length];
        arr1[startPos] = 1;
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < length; j++) {
                long t = arr1[j];
                if (t == 0) {
                    continue;
                }
                if (j > 0) {
                    arr2[j - 1] = (  arr2[j - 1] + t) % 1000000007;
                }
                if (j < length - 1) {
                    arr2[j + 1] =  (  arr2[j + 1] + t) % 1000000007;
                }
            }
            System.arraycopy(arr2, 0, arr1, 0, length);
            Arrays.fill(arr2, 0);
        }
        return (int) arr1[endPos];
    }

}
